package com.LC._493;

//翻转对
class Solution {
    private int count;
    public int reversePairs(int[] nums) {   // 时间复杂度O(nlogn)    空间复杂度O(n)
        if (nums == null || nums.length < 2) {   // 如果数组长度小于2，直接返回0
            return 0;
        }
        count = 0;
        mergeSort(nums, 0, nums.length - 1);    // 对数组进行排序
        return count;
    }
    private void mergeSort(int[] nums, int start, int end) {    // 归并排序
//        System.out.println(start + " " + end);
        if (start == end) {
            return;
        }
        int mid = start + (end - start) / 2;    // 取中间值
        mergeSort(nums, start, mid);    // 对左半部分进行排序
        mergeSort(nums, mid + 1, end);  // 对右半部分进行排序 从这一行开始，就是归并排序
        int i = start;
        int j = mid + 1;
//        {1, 3, 2, 3, 1};
        //如果左侧最后还有剩余元素，则将左侧元素按照从小到大的顺序放入新数组中还要在统计一次
        while (i <= mid && j <= end) {  // 当左右两个数组都有值时，比较左右两个数组的最小值，并将较小值放入新数组
            if ((long) nums[i] > 2 * (long) nums[j]) {  // 如果左半部分的值大于右半部分的值，则左半部分的值与右半部分的值交换
                //其实这里在统计的时候 ,已经是排好序的了，所以可以根据当前 num[i]判断 i之后的元素是否大于2*nums[j]
                count += mid - i + 1;  //i到mid的值都大于nums[j]，所以只需要统计mid-i+1次
                System.out.println(count+" "+nums[i]+" "+nums[j]+" "+(long)nums[i]+(long)nums[j]+" "+(long)nums[i]*2);
                j++;    //考察下一个右j ,为他找 i
            } else {    //当前 i不满足条件，则i++
                System.out.println(count+" "+nums[i]+" "+nums[j]+" "+(long)nums[i]+(long)nums[j]);
                i++;    //考察下一个左i
            }
        }
        // 统计完之后合并
        int[] tempArr = new int[end - start + 1];    // 创建一个临时数组
        i = start;
        j = mid + 1;
        int idx = 0;
        while (i <= mid && j <= end) {  // 当左右两个数组都有值时，比较左右两个数组的最小值，并将较小值放入新数组
            tempArr[idx++] = nums[i] < nums[j] ? nums[i++] : nums[j++];   // 如果左半部分的值小于右半部分的值，则左半部分的值放入新数组
        }
        while (i <= mid) {
            tempArr[idx++] = nums[i++];   // 如果左半部分的值小于右半部分的值，则左半部分的值放入新数组
        }
        while (j <= end) {
            tempArr[idx++] = nums[j++];  // 如果左半部分的值小于右半部分的值，则左半部分的值放入新数组
        }
        for (i = 0, j = start; j <= end; i++, j++) {    // 将新数组的值放入原数组
            nums[j] = tempArr[i];   // 将新数组的值放入原数组
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 3, 1};
        Solution solution = new Solution();
        System.out.println(solution.reversePairs(nums));
    }
}